//
// Created by Administrator on 2021/6/25.
//
#include <vector>
#include <string>
#include <unordered_set>
#include <iostream>
#include <queue>

using namespace std;

class Solution {
public:
    int openLock(vector<string> &deadends, string target) {
        // 目标直接是起点
        if (target == "0000") return 0;
        unordered_set<string> dead(deadends.begin(), deadends.end());
        // 目标或者起始点在dead中
        if (dead.find(target) != dead.end() or dead.find("0000") != dead.end()) return -1;
        // 构造队列
        queue<pair<string, int>> q;
        // 放入初始值
        q.emplace("0000", 0);
        // 记录遇见的状态
        unordered_set<string> seen{"0000"};
        // bfs
        while (!q.empty()) {
            auto[status, level] = q.front();
            q.pop();
            // 迭代时确保每一个入队的状态都是没有遇见过的
            // 找从当前状态可以达到的所有下一个状态
            for (const auto &x : nextStatus(status)) {
                // 找到目标  返回
                if (x == target) return level + 1;
                // 没找到,未见过的状态,入队
                if (seen.find(x) == seen.end() and dead.find(x) == dead.end()) {
                    q.emplace(x, level + 1);
                    seen.insert(x);
                }
            }
        }
        // 找不到
        return -1;
    }

    /**
     * 返回从当前状态出发,可以找到的下一个状态
     * @param curStatus current status 4位
     * @return
     */
    vector<string> nextStatus(string &curStatus) {
        vector<string> ret;
        for (int i = 0; i < 4; ++i) {
            string temp = curStatus;
            char preNum = curStatus[i] == '0' ? '9' : curStatus[i] - 1;
            char nextNum = curStatus[i] == '9' ? '0' : curStatus[i] + 1;
            curStatus[i] = preNum;
            ret.push_back(curStatus);
            curStatus[i] = nextNum;
            ret.push_back(curStatus);
            curStatus = temp;
        }
        return ret;
    }


};

class Solution2 { // 题解
public:
    int openLock(vector<string> &deadends, string target) {
        if (target == "0000") {
            return 0;
        }

        unordered_set<string> dead(deadends.begin(), deadends.end());
        if (dead.count("0000")) {
            return -1;
        }

        auto num_prev = [](char x) -> char {
            return (x == '0' ? '9' : x - 1);
        };
        auto num_succ = [](char x) -> char {
            return (x == '9' ? '0' : x + 1);
        };

        // 枚举 status 通过一次旋转得到的数字
        auto get = [&](string &status) -> vector<string> {
            vector<string> ret;
            for (int i = 0; i < 4; ++i) {
                char num = status[i];
                status[i] = num_prev(num);
                ret.push_back(status);
                status[i] = num_succ(num);
                ret.push_back(status);
                status[i] = num;
            }
            return ret;
        };

        queue<pair<string, int>> q;
        q.emplace("0000", 0);
        unordered_set<string> seen = {"0000"};

        while (!q.empty()) {
            auto[status, step] = q.front(); // 注意这里不要用引用
            q.pop();
            for (auto &&next_status: get(status)) {
                if (!seen.count(next_status) && !dead.count(next_status)) {
                    if (next_status == target) {
                        return step + 1;
                    }
                    q.emplace(next_status, step + 1);
                    seen.insert(move(next_status));
                }
            }
        }

        return -1;
    }
};


int main() {
    vector<string> deadends{"0201", "0101", "0102", "1212", "2002"};
    Solution solution;
    cout << solution.openLock(deadends, "0202");
    return 0;
}